import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
解题思路：二叉树层序遍历的变形
1. 如果是空树直接返回
2. 层序遍历需要用到队列，定义一个队列，里面放置节点的地址，将根节点如队列
3. 队列非空时，循环进行一下操作：
    a. 队列中当前元素都是在同一层的，依次取出遍历，保存到同一个vector中
        取到一个节点时候：
           >> 保存该节点
           >> 如果该节点左子树存在，将该左子树入队列
           >> 如果该节点右子树存在，将该节点右子树入队列
           >> 将当前已遍历节点从队列中拿出来
     b. 本层节点遍历结束后，保存到返回的vector中，此时下一层节点已经全部入队列
*/
class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        // 每层节点保存到一个list中
        List<List<Integer>> ret = new ArrayList<>();
        if(null == root)
            return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            // 遍历当前层中的所有节点，讲下一层的节点入栈
            int size = q.size();   // 本层中的所有节点
            List<Integer> level = new ArrayList<>(size);
            for(int i = 0; i < size; ++i){
                TreeNode cur = q.poll();
                level.add(cur.val);
                // 如果cur的左子树不为空，将左子树入队列
                if(null != cur.left){
                    q.offer(cur.left);
                }
                // 如果cur的右子树不为空，将右子树入队列
                if(null != cur.right){
                    q.offer(cur.right);
                }
            }
            // 本层节点已经遍历完毕，并且下一层的节点已经保存到队列中
            ret.add(level);
        }
        return ret;
    }
}